#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""
from pprint import pprint
import copy


class Solution:

    def numDistinct(self, source, target):
        # return self.numDistinct_rec(source, target)
        # return self.num_distinct_non_rec(source, target)
        # return self.O_n_space_solution(source, target)
        return self.O_2n_space_solution(source, target)

    # =================== 2n space  =====================
    def O_2n_space_solution(self, source, target):
        # 由两行数组构成: 代码清晰可读性好.
        rows, cols = len(target), len(source)
        self.longest = self.make_matrix(2, cols+1, 0)
        self.cnts    = self.make_matrix(2, cols+1, 1)

        for row in range(1, rows+1):
            cur_row = row % 2
            pre_row = (row-1) % 2
            for col in range(1, cols+1):

                left_up_longest = self.longest[pre_row][col-1]
                up_longest = self.longest[pre_row][col]
                left_longest = self.longest[cur_row][col-1]

                left_up_cnt = self.cnts[pre_row][col-1]
                up_cnt = self.cnts[pre_row][col]
                left_cnt = self.cnts[cur_row][col-1]

                cur_match_cnt = 0
                other_match_cnt = 0
                # calc longest
                if target[row-1] == source[col-1]:
                    self.longest[cur_row][col] = left_up_longest + 1
                    cur_match_cnt = left_up_cnt
                else:
                    self.longest[cur_row][col] = max(left_longest, up_longest)

                # calc cnts
                if self.longest[cur_row][col] == up_longest:
                    other_match_cnt = up_cnt
                elif self.longest[cur_row][col] == left_longest:
                    other_match_cnt = left_cnt

                self.cnts[cur_row][col] = cur_match_cnt + other_match_cnt

        return self.cnts[rows % 2][-1]


    # ================= O(n) space  ====================
    def O_n_space_solution(self, source, target):
        rows, cols = len(target), len(source)
        self.longest = [0] * (cols + 1)
        self.cnts    = [1] * (cols + 1)

        left_up_longest = 0
        left_up_cnt = 1

        for row in range(1, rows+1):
            for col in range(1, cols+1):
                left_longest = self.longest[col-1]
                up_longest = self.longest[col]

                left_cnt = self.cnts[col-1]
                up_cnt = self.cnts[col]

                match_cnt = 0
                other_match_cnt = 0

                # calc longest
                if target[row-1] == source[col-1]:
                    self.longest[col] = left_up_longest + 1
                    match_cnt = left_up_cnt
                else:
                    self.longest[col] = max(left_longest, up_longest)

                # calc cnts
                if self.longest[col] == up_longest:
                    other_match_cnt = up_cnt
                elif self.longest[col] == left_longest:
                    other_match_cnt = left_cnt

                # cnts由两部分组成
                self.cnts[col] = match_cnt + other_match_cnt
                left_up_longest = up_longest
                left_up_cnt = up_cnt
        print(self.cnts)
        return self.cnts[-1]

    # =================== non rec  =====================
    def num_distinct_non_rec(self, source, target):
        # write your code here
        rows, cols = len(target), len(source)
        self.longests = self.make_matrix(rows+1, cols+1, 0)
        self.cnts = self.make_matrix(rows+1, cols+1, -1)
        self.source, self.target = source, target

        for row in range(1, rows+1):
            for col in range(1, cols+1):
                if target[row-1] == source[col-1]:
                    self.longests[row][col] = self.longests[row-1][col-1] + 1
                else:
                    self.longests[row][col] = max(self.longests[row-1][col], self.longests[row][col-1])

        # print(self.longests)
        # print(self.longests[-1][-1])
        assert self.longests[-1][-1] == rows
        return self._cnt_rec(rows, cols)

    # =================== rec =====================
    def numDistinct_rec(self, source, target):
        # write your code here
        rows, cols = len(target), len(source)
        self.longests = self.make_matrix(rows+1, cols+1, 0)
        self.cnts = self.make_matrix(rows+1, cols+1, -1)
        self.source, self.target = source, target

        for row in range(1, rows+1):
            for col in range(1, cols+1):
                if target[row-1] == source[col-1]:
                    self.longests[row][col] = self.longests[row-1][col-1] + 1
                else:
                    self.longests[row][col] = max(self.longests[row-1][col], self.longests[row][col-1])

        # print(self.longests)
        # print(self.longests[-1][-1])
        assert self.longests[-1][-1] == rows
        return self._cnt_rec(rows, cols)

    def _cnt_rec(self, row, col):
        if self.cnts[row][col] != -1:
            return self.cnts[row][col]

        if self.longests[row][col] == 0:
            self.cnts[row][col] = 1
            return 1

        if self.target[row-1] == self.source[col-1]:
            left_up = self._cnt_rec(row-1, col-1)
            if max(self.longests[row-1][col], self.longests[row][col-1]) == self.longests[row][col]:
                cnt = left_up + self._cnt_left_or_up(row, col)
            else:
                cnt = left_up
        else:
            cnt = self._cnt_left_or_up(row, col)

        self.cnts[row][col] = cnt
        return cnt


    def _cnt_left_or_up(self, row, col):
        if self.longests[row-1][col] > self.longests[row][col-1]:
            return self._cnt_rec(row-1, col)
        else:
            return self._cnt_rec(row, col-1)


    def make_matrix(self, rows, cols, init_v=None):
        # one_row = [init_v] * cols
        one_row = [copy.deepcopy(init_v) for i in range(cols)]
        matrix = [copy.deepcopy(one_row) for i in range(rows)]
        return matrix


def main():
    print("start main")

    s = Solution()
    # ret = s.numDistinct("daabeddbcedeabcbcbec", "daceeaeeaabbabbacedd")
    ret = s.numDistinct("rabbbit", "rabbit")
    # ret = s.numDistinct("aaaaaaaaaaaaaaaaaaabbbbbbbbbdfadsfjalsdjfalsdjfsadfadf", "aaaaaabbbbbbbbbdfjaldjf")
    ret = s.numDistinct("aaaaaaaaaaaaaaaaaaabbbbbbbbbdfadsfjalsdjfalsdjfsadfadf", "aaaaaabbbbbbbbbdfjaldjf")
    # print(ret)
    assert ret == 1546524

if __name__ == "__main__":
    main()
